We present a real-time algorithm that finds the Penetration Depth (PD)between general polygonal models based on iterative and local optimizationtechniques. Given an in-collision configuration of an object in configurationspace, we find an initial collision-free configuration using several methodssuch as centroid difference, maximally clear configuration, motion coherence,random configuration, and sampling-based search. We project this configurationon to a local contact space using a variant of continuous collision detectionalgorithm and construct a linear convex cone around the projectedconfiguration. We then formulate a new projection of the in-collisionconfiguration onto the convex cone as a Linear Complementarity Problem (LCP),which we solve using a type of Gauss-Seidel iterative algorithm. We repeat thisprocedure until a locally optimal PD is obtained. Our algorithm can processcomplicated models consisting of tens of thousands triangles at interactiverates.
展开▼
